package com.rui.study.algorithm.SORT_2_插入排序;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-11-06 16:17
 **/
public class InsertionSort {

    /**
     * 插入排序：每次将一个元素插入到有序部分正确的位置上。
     * 最好时间复杂度：O(n) ，数据已经有序的情况下
     * 最坏时间复杂度：O(n²)，数据正好是逆序情况下
     * 空间复杂度：O(1)，即原地排序
     * 稳定性：稳定
     * @param a
     */
    public void sort(int[] a) {
        for (int i=1; i<a.length; i++) {
            int tmp = a[i];
            int j=i;
            for (; j>0; j--) {
                if (tmp >= a[j-1]) {
                    break;
                }
                a[j] = a[j-1];
            }
            a[j] = tmp;
        }
    }
}
